Error Decay of (almost) Consistent Signal Estimations from Quantized Gaussian Random Projections

摘要

This paper provides new error bounds on "consistent" reconstruction methodsfor signals observed from quantized random projections. Those signal estimationtechniques guarantee a perfect matching between the available quantized dataand a new observation of the estimated signal under the same sensing model.Focusing on dithered uniform scalar quantization of resolution $\delta>0$, weprove first that, given a Gaussian random frame of $\mathbb R^N$ with $M$vectors, the worst-case $\ell_2$-error of consistent signal reconstructiondecays with high probability as $O(\frac{N}{M}\log\frac{M}{\sqrt N})$ uniformlyfor all signals of the unit ball $\mathbb B^N \subset \mathbb R^N$. Up to a logfactor, this matches a known lower bound in $\Omega(N/M)$ and former empiricalvalidations in $O(N/M)$. Equivalently, if $M$ exceeds a minimal number of framecoefficients growing like $O(\frac{N}{\epsilon_0}\log \frac{\sqrt N}{\epsilon_0})$, any vectors in $\mathbb B^N$ with $M$ identical quantizedprojections are at most $\epsilon_0$ apart with high probability. Second, inthe context of Quantized Compressed Sensing with $M$ Gaussian randommeasurements and under the same scalar quantization scheme, consistentreconstructions of $K$-sparse signals of $\mathbb R^N$ have a worst-case errorthat decreases with high probability as $O(\tfrac{K}{M}\log\tfrac{MN}{\sqrtK^3})$ uniformly for all such signals. Finally, we show that the proximity ofvectors whose quantized random projections are only approximately consistentcan still be bounded with high probability. A certain level of corruption isthus allowed in the quantization process, up to the appearance of a systematicbias in the reconstruction error of (almost) consistent signal estimates.